package com.fyt.algorithm.Leecode.day8_5;

import java.util.HashMap;
import java.util.Map;


public class MinWindow {
    /**
     * 滑动窗口+hash表
     * @param s
     * @param t
     * @return
     */

    //对t建立窗口hash表
 static     Map<Character,Integer>  tMap = new HashMap<>();
    //对s建立遍历hash表
    static   Map<Character,Integer> sMap=new HashMap<>();
    public static String minWindow(String s, String t) {

        //填入tmap,v为元素个数
        for (int i = 0; i <t.length() ; i++) {
            tMap.put(t.charAt(i), tMap.getOrDefault(t.charAt(i),0)+1);
        }
        int l=0,r=-1;
        int minLen=Integer.MAX_VALUE, ansL = -1, ansR = -1;
        //开始滑动窗口
        while (r<s.length()){
            r++;
            if(r<s.length()){
                sMap.put(s.charAt(r),sMap.getOrDefault(s.charAt(r),0)+1);
            }
            //窗口左端开始滑动
            while(check()&&l <= r){
                // 更新最短答案
                if (r - l + 1 < minLen) {
                    minLen = r - l + 1;
                    ansL = l;
                    ansR = r + 1;
                }

                // 出窗口前，减少 s[l] 的计数
                if(tMap.containsKey(s.charAt(l)))
                {
                    sMap.put(s.charAt(l),sMap.get(s.charAt(l))-1);

                }
                ++l;
            }
        }

// 5. 返回结果
        return ansL == -1 ? "" : s.substring(ansL, ansR);
    }
    public static boolean check() {
        for (Map.Entry<Character,Integer> entry : tMap.entrySet()) {
            char key = entry.getKey();
            int need = entry.getValue();
            if (sMap.getOrDefault(key, 0) < need) {
                // 只要有一个不满足，就立刻返回 false
                return false;
            }
        }
        // 全部满足，才返回 true
        return true;
    }



    public static void main(String[] args) {
        String s = "ADOBECODEBANC", t = "ABC";
        System.out.println(minWindow(s,t));
    }
}
